/*
    双端队列

    一种特殊的队列, 允许同时操作队列头与队列尾;
    类似栈和队列的结合体
    本次准备写两个版本, 单独实现和继承队列
 */

/**
 * 单独实现双端队列
 */

interface DequeItems<T> {
    [index: number]: T
}

class Deque<T = any> {
    items: DequeItems<T> = {};
    current: number = 0;
    lastCurrent: number = 0;

    constructor(...args: T[]) {
        this.addBack(...args)
    }

    /**
     * 向队首追加
     */
    addFront(...args: T[]): void {
        if (!args.length) return;
        if (this.isEmpty()) {
            this.addBack(...args);
        }

        if (this.lastCurrent >= args.length) {
            for (let i = args.length - 1; i >= 0; i--) {
                this.lastCurrent--;
                this.items[this.lastCurrent] = args[i];
            }
        } else {
            const af_num = args.length - this.lastCurrent;
            this.itemsBack(af_num);
            this.addFront(...args);
        }
    }

    /**
     * item向后移动N位
     */
    itemsBack(num: number): void {
        for (let i = this.current - 1; i >= this.lastCurrent; i--) {
            this.items[i + num] = this.items[i]
        }
        this.current += num;
        this.lastCurrent += num;
    }

    /**
     * 向末尾追加
     */
    addBack(...args: T[]): void {
        if (!args.length) return;
        for (let i = 0; i < args.length; i++) {
            this.items[this.current] = args[i];
            this.current++
        }
    }

    /**
     * 删除队首元素
     */
    removeFront(rmIndex?: number): T | undefined {
        let index = rmIndex ?? this.lastCurrent
        if (this.isEmpty()) return undefined;
        let item = this.items[index];
        delete this.items[index];
        !rmIndex && this.lastCurrent++;
        return item;
    }

    /**
     * 删除末尾元素
     */
    removeBack(): T | undefined {
        if (this.isEmpty()) return undefined;
        this.current--;
        return this.removeFront(this.current);
    }

    /**
     * 查看队首元素
     */
    peekFront(showIndex?: number) {
        let index = showIndex ?? this.lastCurrent
        if (this.isEmpty()) return undefined;
        return this.items[index];
    }

    /**
     * 查看队尾元素
     */
    peekBack(): T | undefined {
        return this.peekFront(this.current - 1)
    }

    /**
     * 判断是否为空
     */
    isEmpty(): boolean {
        return this.size() === 0;
    }


    /**
     * 获取大小
     */
    size(): number {
        return this.current - this.lastCurrent;
    }

    /**
     * 清空数据
     */
    clear() {
        this.items = {};
        this.current = 0;
        this.lastCurrent = 0;
    }

    /**
     * 输出
     */
    toString(): string {
        if (this.isEmpty()) return "";
        let str = "";
        for (let i = 0, len = this.size(); i < len; i++) {
            str += this.items[this.lastCurrent + i];
            str += ","
        }
        str = str.substr(0, str.length - 1)
        return str;
    }

}

let deque = new Deque(1, 2, 3);
console.log("初始化成功, 查看长度", deque.size())
console.log("查看元素", deque.toString());
console.log("查看是否为空", deque.isEmpty());
deque.addFront(233, 2333);
console.log("向队首添加元素成功,查看长度", deque.size());
console.log("查看元素", deque.toString());
deque.addFront(2332, 23332);
console.log("向队首添加元素成功,查看长度", deque.size());
console.log("查看元素", deque.toString());

console.log("弹出队首元素", deque.removeFront());
console.log("弹出队首元素成功,查看长度", deque.size());

deque.addFront(2333, 23333);
console.log("向队首添加元素成功,查看长度", deque.size());
console.log("查看元素", deque.toString());
deque.addBack(12, 123);
console.log("向队尾添加元素成功,查看长度", deque.size());
console.log("查看元素", deque.toString());
console.log("弹出队首元素", deque.removeFront());
console.log("弹出队首元素成功,查看长度", deque.size());
console.log("查看元素", deque.toString());
console.log("弹出队尾元素", deque.removeBack());
console.log("弹出队尾元素成功,查看长度", deque.size());
console.log("查看元素", deque.toString());
console.log("查看此时队首元素", deque.peekFront());
console.log("查看此时队尾元素", deque.peekBack());
console.log("清空队列")
deque.clear();
console.log("查看长度", deque.size())
console.log("查看是否为空", deque.isEmpty());
